package com.jiang.daily.Q120;

import java.util.List;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/09/25 11:20
 */
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        for (int i = 1; i < len; i++) {
            List<Integer> now = triangle.get(i);
            List<Integer> pre = triangle.get(i - 1);
            for (int j = 0; j <= i; j++) {
                int present = now.get(j);
                if (j == 0) {
                    now.set(j, present + pre.get(j));
                } else if (j == i) {
                    now.set(j, present + pre.get(j - 1));
                } else {
                    now.set(j, present + Math.min(pre.get(j - 1), pre.get(j)));
                }
            }
        }

        int res = Integer.MAX_VALUE;
        List<Integer> temp = triangle.get(len - 1);
        for (int i = 0; i < len; i++) {
            res = Math.min(res, temp.get(i));
        }
        return res;
    }
}
